Algoritmo in loco

In informatica un algoritmo si dice in loco oppure in place quando è in grado di trasformare una struttura dati utilizzando soltanto un piccolo e costante spazio di memoria extra. I dati in ingresso sono solitamente sovrascritti con il risultato prodotto durante l'esecuzione dell'algoritmo.

Un algoritmo è a volte chiamato in modo informale in loco quando sovrascrive i suoi input con i suoi output. In realtà questo non è sufficiente (come dimostra il caso del quicksort) né è necessario; la quantità di spazio occupato dall'output potrebbe essere costante, oppure potrebbe non essere nemmeno quantificabile, per esempio nel caso di output su stream. D'altro canto a volte potrebbe essere più pratico quantificare lo spazio occupato dai risultati in output e determinare se l'algoritmo è definibile come in loco, come si vede nell'esempio di rovesciamento sottostante.

Gli algoritmi in loco sono più efficienti in termini di memoria e, spesso, anche in termini di CPU, rispetto alle controparti non in loco e tendono quindi ad essere preferiti rispetto a questi ultimi.

Esempio

Supponiamo di dover rovesciare un array di n elementi. Questo è un modo semplice:

function rovescia(a[0..n])

alloca b[0..n]

for i from 0 to n

b[n - i] = a[i]

return b

Sfortunatamente questo richiede O(n) spazio per creare b e l'allocazione è anche spesso un'operazione lenta. Se nel seguito del programma non abbiamo più necessità di conservare a possiamo sovrascriverlo con il suo rovescio utilizzando un algoritmo in loco:

function rovescia-in-loco(a[0..n])

for i from 0 to int(n/2)

swap(a[i], a[n-i])

Alcuni algoritmi in loco

Ecco una serie di algoritmi di ordinamento che operano in loco:

• Bubble sort
• Insertion sort
• Quicksort
• Selection sort
• Counting sort. Ha anche una controparte non in loco, leggermente più efficiente in termini di CPU ma con la stessa complessità (lineare)
• Heap sort
• Shell sort